package 力扣_高阶数据结构.优先级队列;

import java.util.*;

/**
 * @author zx
 * @create 2022-08-15 20:43
 */
public class 前K个高频单词_692 {
    /**
     * @return 这个题应该是优先级队列中最难的
     * 优先级队列这类队列里存储不是同一类型的参数的题,感觉还是使用map对value排序的方式简单点
     * 使用优先级队列细节太多了
     */
    public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length;i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        PriorityQueue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                if(o1.count != o2.count){
                    return o1.count - o2.count;
                }else{
                    return o2.str.compareTo(o1.str);//因为要比较字典序,多个这个
                }
            }
        });
        //因为这里key,value类型不相同,所以queue不能存储数组,只能新建一个类,将key,value封装为类属性
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            int value = entry.getValue();
            if (queue.size() < k) {
                queue.offer(new Freq(key, value));
            } else{
                Freq peek = queue.peek();
                if(value < peek.count){
                    continue;
                }else if(value == peek.count){
                    //出现次数相同, 比较字典顺序！
                    String str = peek.str;
                    if(key.compareTo(str) < 0){
                        queue.poll();
                        queue.offer(new Freq(key,value));
                    }
                }else{
                    queue.poll();
                    queue.offer(new Freq(key,value));
                }
            }
        }
        for(int i = 0;i < k;i++){
            res.add(queue.poll().str);
        }
        Collections.reverse(res);
        return res;
    }
    class Freq{
        String str;
        int count;
        public Freq(String key, int value){
            this.str = key;
            this.count = value;
        }
    }

    /**
     * @return 对map中的value排序
     */
    public List<String> topKFrequent2(String[] words, int k) {
        List<String> res = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0;i < words.length;i++){
            map.put(words[i],map.getOrDefault(words[i],0) + 1);
        }
        List<Map.Entry<String,Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue() != o2.getValue()){
                    //频率逆序排序
                    return o2.getValue() - o1.getValue();
                }else{
                    //字典顺序排序
                    return o1.getKey().compareTo(o2.getKey());
                }
            }
        });
        for(int i = 0;i < k;i++){
            res.add(entries.get(i).getKey());
        }
        return res;
    }
}